package airthmetic.exercise.linkedList;

public class _234_回文链表 {


    public static boolean isPalindrome(ListNode head) {
        // 短路判断
        if (head == null || head.next == null) return true;
        if (head.next.next == null) return head.val == head.next.val;

        // 找到中间节点
        ListNode mid = a(head);
        // 反转中心节点下一个节点
        ListNode rNode = b(mid.next);
        ListNode lNode = head;
        ListNode oldRNode = rNode;

        Boolean isPalindrome = true;
        while (rNode != null) {
            if (rNode.val != lNode.val){
                isPalindrome = false;
                break;
            }
            rNode = rNode.next;
            lNode = lNode.next;
        }

        // 反转回去 不破坏原结构
        b(oldRNode);

        return isPalindrome;
    }

    private static ListNode b(ListNode head) {
        ListNode newHead = null;
        // 下一个元素临时变量 (两个作用：
        //                          1.这里为了保留内存地址指向,否则可能会被gc回收
        //                          2.下一个元素需要再循环末尾覆盖掉循环对象 形成循环)
        ListNode temp;
        while (head != null) {
            // 1.拿到下一个元素
            temp = head.next;
            // 2.head的next指向newHead(第一次是null，之后newHead被赋值为上次循环的head[第3步])
            head.next = newHead;
            // 3. 当前执行逻辑head赋值给上一个head
            newHead = head;
            // 当前元素指向 下一个元素(下一个元素赋值到循环对象)
            head = temp;
        }
        return newHead;
    }

    private static ListNode a(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public static boolean isPalindrome2(ListNode head) {
        if(head == null){
            return false;
        }

        ListNode fastNode = head;
        ListNode slowNode = head;
        ListNode prev = null;
        ListNode current = null;
        while(fastNode != null && fastNode.next != null){

            current = slowNode;
            fastNode = fastNode.next.next;
            slowNode = slowNode.next;

            current.next = prev;
            prev = current;
        }

        if(fastNode != null){
            slowNode = slowNode.next;
        }
        while(slowNode != null){
            if(slowNode.val != current.val){
                return false;
            }
            slowNode = slowNode.next;
            current = current.next;
        }

        return true;
    }



    public static void main(String[] args) {
//        ListNode listNode6 = new ListNode(1, null);
//        ListNode listNode5 = new ListNode(1, null);
        ListNode listNode4 = new ListNode(1, null);

        ListNode listNode3 = new ListNode(2, listNode4);
        ListNode listNode2 = new ListNode(2, listNode3);
        ListNode listNode = new ListNode(1, listNode2);

       /* System.out.println(listNode);
        System.out.println(isPalindrome(listNode));
        System.out.println(listNode);*/


        System.out.println(isPalindrome2(listNode));
    }
}
